/**
 *
 *   Copyright (C) 2011 by Wilk Maia
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 *
 * File: avl_tree.cpp
 * Author: Wilk Maia
 * E-mail: wilkmaia@gmail.com
 * Version: 1.0.0
 * Date: 14/02/2011
 * 
 * This file is under CreativeCommons Attribution CC BY License and MIT License
 * 
 */

#ifndef __AVL_TREE_CPP__
#define __AVL_TREE_CPP__

#include "avl_tree.hpp"


/**
 * AVL_No class methods
 */
AVL_No::AVL_No( const int& id )
{
	this->itemId = id;
	this->left = this->right = NULL;
	this->heigth = 0;
}
AVL_No::AVL_No( const int& id, AVL_No *l, AVL_No *r, const char& h )
{
	this->itemId = id;
	this->left = l;
	this->right = r;
	this->heigth = h;
}
AVL_No::~AVL_No()
{
	delete this->left;
	delete this->right;
}
int AVL_No::getValue()
{
	return this->itemId;
}
char AVL_No::getHeigth()
{
	return this->heigth;
}
void AVL_No::setId( int id )
{
	this->itemId = id;
}

/**
 * AVL_Tree class methods
 */
AVL_Tree::AVL_Tree()
{
	this->root = NULL;
}
AVL_Tree::~AVL_Tree()
{
	this->clear();
}
char AVL_Tree::heigth( AVL_No* node )
{
	return node == NULL ? -1 : node->getHeigth();
}
AVL_Tree* AVL_Tree::avlInit( const string& filePatch )
{
	ifstream myFile( filePatch.c_str() );
	string itemIdString, buffer;
	int k;

	if( !myFile.is_open() )
	{
		cout << "\nErro ao carregar a database de itens...";
		cout << "Nome do arquivo: " << filePatch;
		return NULL;
	}

	cout << "\n\t\t -- Carregando a database de itens... --\n";
	for( k = 0 ; !myFile.eof(); k = 0 )
	{
		buffer.clear();

		getline( myFile, buffer );
		k = buffer.find_first_of( ",", 0 );

		itemIdString = buffer.substr( 0, k );
		k = atoi( itemIdString.c_str() );

		this->avlInsert( k, this->root );
	}
	myFile.close();
	cout << "\n\t\t -- Database de itens carregada. --\n";

	return this;
}
bool AVL_Tree::avlInsert(const int& id, AVL_No*& node = root)
{
	if( node == NULL )
	{
		node = new AVL_No( id );
	}
	else
	if( id < node->getValue() )
	{
		this->avlInsert( id, node->left );
		if( this->heigth( node->left ) - this->heigth( node->right ) == 2 )
		{
			if( id < node->getValue() )
				this->singleRotate( node, LEFT );
			else
				this->doubleRotate( node, LEFT );
		}
	}
	else
	if( id > node->getValue() )
	{
		this->avlInsert( id, node->right );
		if( this->heigth( node->right ) - this->heigth( node->left ) == 2 )
		{
			if( id > node->getValue() )
				this->singleRotate( node, RIGHT );
			else
				this->doubleRotate( node, RIGHT );
		}
	}
	else
		;

	node->heigth = max( this->heigth( node->left ), this->heigth( node->right ) ) + 1;
	return true;
}
void AVL_Tree::singleRotate( AVL_No*& node, bool dir )
{
	switch( dir )
	{
		AVL_No* buf;
		case LEFT:
			buf = node->left;
			node->left = buf->right;
			buf->right = node;
			node->heigth = max( this->heigth( node->left ), this->heigth( node->right ) ) + 1;
			buf->heigth = max( this->heigth( buf->left ), this->heigth( buf->right ) ) + 1;
			node = buf;
			break;

		case RIGHT:
			buf = node->right;
			node->right = buf->left;
			buf->left = node;
			node->heigth = max( this->heigth( node->left ), this->heigth( node->right ) ) + 1;
			buf->heigth = max( this->heigth( buf->left ), this->heigth( buf->right ) ) + 1;
			node = buf;
			break;
	}
}
void AVL_Tree::doubleRotate( AVL_No*& node, bool dir )
{
	switch( dir )
	{
		case LEFT:
			this->singleRotate( node->left, RIGHT );
			this->singleRotate( node, LEFT );
			break;

		case RIGHT:
			this->singleRotate( node->right, LEFT );
			this->singleRotate( node, RIGHT );
			break;
	}
}
void AVL_Tree::clear()
{
	delete this->root;
	this->root = NULL;
}
bool AVL_Tree::avlRemove( const int& id, AVL_No*& node )
{
	if( node == NULL )
		return false;
	else
	if( id < node->getValue() )
	{
		this->avlRemove( id, node->left );
		if( heigth( node->left ) - heigth( node->right ) == 2 )
		{
			if( heigth( node->right.left ) <= heigth( node->right.right ) )
				this->singleRotate( node, RIGHT );
			else
				this->doubleRotate( node, RIGHT );
		}
	}
	else
	if( id > node->getValue() )
	{
		this->avlRemove( id, node->right );
		if( heigth( node->left ) - heigth( node->right ) == 2 )
		{
			if( heigth( node->left.right ) <= heigth( node->left.left ) )
				this->singleRotate( node, LEFT );
			else
				this->doubleRotate( node, LEFT );
		}
	}
	else
	if( node->left == NULL || node->right == NULL )
	{
		AVL_No* buf = node;
		node = ( node->left != NULL ) ?	node->left : node->right;
		delete buf;
	}
	else
	{
		AVL_No* buf = node->left;
		
		for( ; buf->right != NULL; )
			buf = buf->right;
		
		node->setId( buf->getValue() );
		this->avlRemove( node->getValue(), node->left );

		if( heigth( node->left ) - heigth( node->right ) == 2 )
		{
			if( heigth( node->left.right ) <= heigth( node->left.left ) )
				this->singleRotate( node, LEFT );
			else
				this->doubleRotate( node, LEFT );
		}
	}
}
bool AVL_Tree::avlSearch( const int& id )
{
	AVL_No* parser = this->root;

	for( ; parser != NULL; )
	{
		if( id > parser.getValue() )
			parser = parser->left;
		else
		if( id < parser.getValue() )
			parser = parser->right;
		else
			return true;
	}
	return false;
}

#endif // __AVL_TREE_CPP__